import java.util.Scanner;

/**
 * Created by L.jp
 * Description:
 * ①：链接：https://www.nowcoder.com/questionTerminal/9ae56e5bdf4f480387df781671db5172
 * 来源：牛客网
 * ②：https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a
 *
 * ③：https://ac.nowcoder.com/questionTerminal/8cb175b803374e348a614e34b80ae191
 *
 * 这三个题都是一样的解法
 * 我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
 * 例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。
 * 现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。
 * User: 86189
 * Date: 2022-04-14
 * Time: 20:45
 */
public class Main {
    /*  这个题目最经典的解法就是动态规划，要求两个字符串的最长公共子序列，那么就问题就转化为要求s1的前i个字符中和s2的前j个字符中的最长公共子序列
        所以就可以构造一个dp数组存储两个字符串对应位置下的当前的最长公共子序列的长度
        构造数组如下：
                null    a   b   c   f   b   c
    *               0   0   0   0   0   0   0
                a   0   1   1   1   1   1   1
                b   0   1   2   2   2   2   2
                f   0   1   2   2   3   3   3
                c   0   1   2   3   3   3   4
                a   0   1   2   3   3   3   3
                b   0   1   2   3   3   4   4----->这就是我们要的答案 :可以根据状态方程求出来
                
    *
    * */
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            String m=scanner.next();
            String n=scanner.next();
            int len1=m.length();
            int len2=n.length();
            int[][] dp=new int[len1+1][len2+1];
            //构造dp数组，dp[i][j]表示m的前i个字符和n的前j个字符的最长公共子序列的长度
            for(int i = 1;i<=len1;i++){
                for(int j = 1; j <= len2; j++){
                    if(m.charAt(i-1)==n.charAt(j-1)){
                        //如果对应位置的字符相等，那么s1的前i个字符和s2的前j个字符中，最长公共子序列的长度就是前一位置存储的最长公共子序列长度+1
                        dp[i][j]=dp[i-1][j-1]+1;
                    }else{
                        //如果对应位置字符不相等，那么就最长公共子序列就是s1的前i个字符和s2的前j-1个字符中的最长公共子序列，
                        // 还有s1的前i-1个字符和s2的前j个字符中的最长公共子序列，两者取最大值
                        dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
            System.out.println(dp[len1][len2]);
        }
    }
}
